\chapter{Introduzione}
Il Problema del Commesso Viaggiatore (Traveling Salesman Problem, TSP) è probabilmente il problema di ottimizzazione più noto, a causa della sua formulazione di immediata comprensione, della sua impostazione molto ``visuale'' e di un campo di applicabilità che spazia dalla logistica alla bioinformatica che lo rendono adatto come benchmark, anche dal punto di vista didattico, per diverse tecniche di risoluzione.

Obiettivo del TSP è trovare il ciclo hamiltoniano di costo minimo in un grafo completo, cioè il percorso che tocca tutti i nodi del grafo e torna al nodo di partenza, selezionando l'ordine dei nodi (e quindi gli archi attraversati) in maniera tale che la somma totale dei costi degli archi attraversati sia la più bassa possibile.

Il TSP (nella sua versione simmetrica) è matematicamente definito per un grafo completo $G = (V,E)$ come:
\begin{equation}
  \min \sum_{e \in E}c_ex_e \label{eqn:of}
\end{equation}
rispetto a
\begin{align}
  \sum_{e \in \delta(v)} & x_e = 2 \quad\forall\: v \in V \label{eqn:degconst}\\
  \sum_{e \in E(S)} & x_e \leq |S| - 1 \quad\forall\: S \subset V,\; S \neq \emptyset \label{eqn:modelsecs}\\
  & x_e \in \{0,1\}  \quad \forall\: e \in E. \label{eqn:integer}
\end{align}
Nella funzione obiettivo \ref{eqn:of} le variabili $x_e$ sono variabili indicatrici intere (vincolo \ref{eqn:integer}) associate agli archi che assumono valore 1 se l'arco corrispondente è selezionato nella soluzione ottima e 0 altrimenti, e $c_e$ è il costo loro associato. Il vincolo di grado \ref{eqn:degconst} impone che su nodo incidano due e solo due archi, mentre la famiglia di vincoli \ref{eqn:modelsecs} vieta la presenza di cicli di dimensione inferiore a $|V|$. Ci sono più modi per specificare questa condizione, oltre alla formulazione di tipo knapsack qui riportata; questi vincoli prendono il nome di SECs, sigla per subtour elimination constraints.

Il TSP è un problema NP-completo: ciò significa che al giorno d'oggi un algoritmo efficiente non è ancora conosciuto, e forse non esiste nemmeno. Il numero di possibili tour definibili su un grafo cresce in maniera proporzionale al fattoriale del numero di nodi, pertanto un approccio brute-force è impraticabile anche solo per grafi di pochi nodi. Negli anni, moltissimi autori hanno approcciato il problema con varie tecniche spesso innovative, come ad esempio il branch-and-cut in \citet*{padberg1991branch}; tuttavia, anche l'algoritmo ad oggi più efficiente fallisce quando eseguito su istanze molto grandi. Per istanze di prova di centinaia di migliaia o milioni di nodi, attualmente non è ancora conosciuta la soluzione ottima\footnote{si veda http://www.math.uwaterloo.ca/tsp/}. Una cronologia dei vari approcci al problema, nonché una vasta presentazione delle tecniche, si trova in \citet*{applegate2011traveling}, volume accompagnato dal software Concorde\footnote{http://www.math.uwaterloo.ca/tsp/concorde.html} \citep{applegate2006concorde}, attualmente il più efficace risolutore di istanze di TSP.

In questa relazione esponiamo alcune di queste tecniche, sviluppate durante il corso di Ricerca Operativa 2, accompagnate da risultati computazionali e relative considerazioni. Le varie tecniche sono state implementate in linguaggio \texttt{c}, usando nella seconda parte del corso i metodi per usare il solver IBM ILOG CPLEX\texttrademark 12.5\footnote{http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/}. I test sono stati effettuati su istanze della libreria TSPLIB (\citet*{reinelt1991tsplib}), che contiene diverse istanze note del TSP, con dimensioni che vanno dalle poche decine alle migliaia di nodi, che viene normalmente usata come riferimento per i lavori su TSP presenti in letteratura. In particolare, le tecniche sviluppate durante il corso vengono testate su un testbed di istanze geografiche ed euclidee (in cui i costi rispettano la disuguaglianza triangolare) di taglia inferiore ai 1000 nodi.

La relazione è strutturata come segue: nel capitolo 2 è descritto il primo approccio è basato sul rilassamento lagrangiano del problema, sul quale si costruisce un algoritmo branch-and-bound.  Nel capitolo 3 il problema viene formulato come problema di programmazione mista intera, e vengono presentate alcune tecniche per la sua risoluzione esatta. Nel capitolo 4 invece si presentano alcune tecniche euristiche per la risoluzione del TSP. Infine, esponiamo le conclusioni ottenute.
